#pragma once

#include <iostream>
using namespace std;

typedef struct BinarySearchTreeNode {
    int data;
	BinarySearchTreeNode* Parent;
    BinarySearchTreeNode* LChild;
    BinarySearchTreeNode* RChild;
}BSTNode;

//传入头节点, 往头节点中按 二叉排序树(小的在左, 大的在右)的规则 插入节点
void BSTInsert(BSTNode *T, int data) {
    if (T == nullptr)
		return;

	if (T->data > data) {
		if (T->LChild == nullptr) {
			T->LChild = new BSTNode();
			T->LChild->data = data;
			T->LChild->Parent = T;
			T->LChild->LChild = nullptr;
			T->LChild->RChild = nullptr;
		}
		else {
			BSTInsert(T->LChild, data);
		}
	}
	
	else {
		if (T->RChild == nullptr) {
			T->RChild = new BSTNode();
			T->RChild->data = data;
			T->RChild->Parent = T;
			T->RChild->LChild = nullptr;
			T->RChild->RChild = nullptr;
		}
		else {
			BSTInsert(T->RChild, data);
		}
	}

}

//寻找前驱节点
BSTNode* FindPrecursor(BSTNode* root) {
	/*
	* 若一个结点有左子树，那么该结点的前驱节点是其左子树中val值最大的结点
	* 即左子树中最右边的结点
	*/
	if (root->LChild != nullptr) {
		root = root->LChild;
		while (root->RChild != nullptr)
			root = root->RChild;

		return root;
	}

	//没有左子树
	else {
		/*
		* 若该结点是其父结点的右孩子，那么该结点的前驱结点即为其父结点
		*/
		if (root == root->Parent->RChild)
			return root->Parent;

		/*
		* 若该结点是其父结点的左孩子
		* 那么需要沿着其父结点一直向树的顶端寻找
		* 直到找到一个结点P，P结点是其父结点Q的右孩子，那么Q就是该结点的前驱结点
		*/
		else {
			while (root->Parent != nullptr) {
				root = root->Parent;
				if (root == root->Parent->RChild)
					return root->Parent;
			}
		}
	}

	return nullptr;
}

//寻找后继节点
BSTNode* FindPosterior(BSTNode* root) {
	/*
	* 若一个结点有右子树，那么该结点的后继节点是其右子树中val值最小的结点
	*/
	if (root->RChild != nullptr) {
		root = root->RChild;
		while (root->LChild != nullptr)
			root = root->LChild;

		return root;
	}

	//右子树不存在
	else {
		/*
		* 若该结点是其父结点的左孩子，那么该节点的后继结点即为其父节点
		*/
		if (root == root->Parent->LChild)
			return root->Parent;

		/*
		* 若该结点是其父结点的右孩子
		* 那么需要沿着其父结点一直向树的顶端寻找
		* 直到找到一个结点P，P结点是其父结点Q的左孩子，那么Q就是该结点的前驱结点
		*/
		else {
			while (root->Parent != nullptr) {
				root = root->Parent;
				if (root < root->Parent->LChild)
					return root->Parent;
			}
		}
	}

	return nullptr;
}

//删除节点
void BSTDelete(BSTNode*& root, int data) {
	if (root == nullptr)
		return;

	if (root->data > data)
		BSTDelete(root->LChild, data);

	else if (root->data < data)
		BSTDelete(root->RChild, data);

	/*
	* 判断删除的节点的类型：
	*	1.左右子树存在
	*	2.只存在 左 / 右 子树
	*	3.叶子节点
	*/
	else {
		//左右子树都存在时
		if (root->LChild != nullptr && root->RChild != nullptr) {
			//在这里寻找后继节点, 来代替被删除节点
			BSTNode* posterior = FindPosterior(root);

			//当后继节点为父节点, 也就是说被删除节点没有右子树时
			//if (posterior == root->Parent) {
			//	posterior->LChild = root->LChild;
			//	delete root;
			//}
			//不需要判断, 只有一个子树的节点的后继节点才会是父节点, 会走下一层判断

			//后继节点为叶子节点, 即后继节点没有右子树(肯定没有左子树)
			//后继节点为被删除节点的孩子节点
			//替换数据, 删除后继节点
			if (posterior->RChild == nullptr || root->RChild == posterior) {
				root->RChild = posterior->RChild;
				root->data = posterior->data;
				delete posterior;
			}

			//后继节点拥有右子树, 即不为叶子节点
			//并且不为被删除节点的孩子节点
			//将后继节点的右子树 赋值给 其父节点的左子树(必定是左子树)
			//删除后继节点
			else {
				posterior->Parent->LChild = posterior->RChild;
				root->data = posterior->data;
				delete posterior;
			}
		}

		/*
		* 只有 左 / 右 子树时
		* 将 左 / 右 子树赋值给父节点
		*/
		else {
			BSTNode* deleteNode = root;
			if (root->LChild == nullptr) {
				if (root->Parent->RChild == root)
					root->Parent->RChild = root->RChild;

				else
					root->Parent->LChild = root->RChild;

				delete deleteNode;
			}

			else if (root->RChild == nullptr) {
				if (root->Parent->RChild == root)
					root->Parent->RChild = root->LChild;

				else
					root->Parent->LChild = root->LChild;

				delete deleteNode;
			}

			//叶子节点	直接删除
			else {
				if (root == root->Parent->RChild) {
					root->Parent->RChild = nullptr;
					delete deleteNode;
				}

				else {
					root->Parent->LChild = nullptr;
					delete deleteNode;
				}
			}
		}
	}
}

//二叉树前序遍历
void PreTravelBinarySearchTree(BSTNode* T) {
    if (T != nullptr) {
        cout << T->data << " ";
        PreTravelBinarySearchTree(T->LChild);
        PreTravelBinarySearchTree(T->RChild);
    }
}

//二叉树中序遍历
void InTravelBinarySearchTree(BSTNode* T) {
    if (T != nullptr) {
        InTravelBinarySearchTree(T->LChild);
        cout << T->data << " ";
        InTravelBinarySearchTree(T->RChild);
    }
}

//二叉树后序遍历
void BackTravelBinarySearchTree(BSTNode* T) {
    if (T != nullptr) {
        BackTravelBinarySearchTree(T->LChild);
        BackTravelBinarySearchTree(T->RChild);
        cout << T->data << " ";
    }
}

//==============================cpp实现
class BSTNodeTree {
public:
	BSTNode* Head;

public:
	BSTNodeTree() {
		Head = nullptr;
	}

	//迭代方式插入节点
	void InsertNode(int data) {
		//头节点为空时初始化头节点
		if (Head == nullptr) {
			BSTNode* node = new BSTNode();
			node->data = data;
			node->LChild = nullptr;
			node->RChild = nullptr;

			Head = node;
			return;
		}

		//循环遍历
		BSTNode* prePNode = nullptr;
		BSTNode* pNode = Head;
		bool isLeft = true;
		while (pNode != nullptr) {
			prePNode = pNode;
			if (data < pNode->data) {
				pNode = pNode->LChild;
				isLeft = true;
			}
			else {
				pNode = pNode->RChild;
				isLeft = false;
			}
		}

		//判断在插入节点位置在 左/右 ?
		if (isLeft) {
			prePNode->LChild = new BSTNode();
			prePNode->LChild->data = data;
			prePNode->LChild->LChild = nullptr;
			prePNode->LChild->RChild = nullptr;
		}
		else {
			prePNode->RChild = new BSTNode();
			prePNode->RChild->data = data;
			prePNode->RChild->LChild = nullptr;
			prePNode->RChild->RChild = nullptr;
		}
	}
};